/*!  \file  Task.cpp
 *	  \brief  
 * 
 *   \details   details
 *   \author    Yordan Madzhunkov German Research School for Simulation Sciences GmbH
 *   \version   1.0
 *   \date      07/16/2013 04:14:45 PM
 *   \copyright GNU Public License.
 */
#include <pthread.h>
#include <assert.h>
#include <iostream>
#include <assert.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>
#include <iomanip>
#include <stdio.h>
#include "Lock.h"
#include "Task.h"
#include "CompileTime.h"
#include "Matrix.h"
#include "GK.h"
#include "Queue.h"
#include "MemoryPool.h"
#include "BiMRRR.h"
#include "TaskManager.h"
#include "UnitTester.h"
#include "GKManager.h"
#define CASE_SET_POINTERS(x)  \
		case x : {\
			computeF = &Task::compute##x;\
			childF   = &Task::child##x;\
			finishF  = &Task::finish##x;\
			break;\
		}
#pragma GCC diagnostic ignored "-Wunused-parameter"

using namespace std;
void Task::reset(Type type_,	void * dataPtr_, int localID_, TaskID parentID_){
	assert(type_ < End);
	type = type_;
	dataPtr  = dataPtr_;
	localID  = localID_;
	parentID = parentID_;
	count = 0;
 	switch (type) {
		CASE_SET_POINTERS(  CountWithBisector           );
		CASE_SET_POINTERS(  RefineIntervalWithBisector  );
		CASE_SET_POINTERS(  SplitIntervalWithBisector   );
		CASE_SET_POINTERS(  IdentifyClusters            );
		CASE_SET_POINTERS(  ShiftRepresentation         );
		CASE_SET_POINTERS(  RefineSingletonWithGK       );
		CASE_SET_POINTERS(  ComputeSingleton             );
		CASE_SET_POINTERS(  ComputeCluster              );
		CASE_SET_POINTERS(  BiMRRRTask                  );
		case End : {                   
			assert(false);
		}
	}
}
	static const char * types[] = {
		"CountWithBisector          ",
		"RefineIntervalWithBisector ", 
		"SplitIntervalWithBisector  ", 
		"IdentifyClusters           ", 
		"ShiftRepresentation        ", 
		"RefineSingletonWithGK      ", 
		"ComputeSingleton            ", 
		"ComputeCluster             ", 
		"BiMRRRTask                 "
	};
std::ostream& operator<<(std::ostream& os, const Task & t) {
	char buf[256];
	sprintf(buf, "Task %s data=%p localID=%d parent=%d tID=%d count=%d\n", 
		types[t.type], t.dataPtr, t.localID, t.parentID, t.threadID, t.count);
	os << buf;  
	return os;
}

void Task::setCount(TaskManager & man, const int val      ){ // thread safe
	Lock & lock = man.getLock(this);
	lock.lock();
	count = val;
	lock.unlock();
}
int Task::addCount(TaskManager & man, const int updateVal){ // thread safe
	Lock & lock = man.getLock(this);
	lock.lock();
	int res = (count += updateVal);
	lock.unlock();
	return res;
}
void Task::print(std::ostream& os, const int taskID) {
	char buf[256];
	Task &t = *this; // how lame
	sprintf(buf, "TaskID=%3d %s data=%p localID=%d parent=%d tID=%d count=%d\n",
		taskID, types[t.type], t.dataPtr, 
		t.localID, t.parentID, t.threadID, t.count);
	os << buf;  
}
bool Task::computeRefineSingletonWithGK(TaskManager& manager) {

	return true;
}
bool Task::childRefineSingletonWithGK(TaskManager&, const TaskID childID) {

	return true;
}
void Task::finishRefineSingletonWithGK(TaskManager & man) {

}

bool Task::computeRefineIntervalWithBisector(TaskManager& manager) {
	reinterpret_cast<GKBisector*>(dataPtr)->refine(localID);
	return true;
}
bool Task::childRefineIntervalWithBisector(TaskManager&, const TaskID childID) {	

assert(false);}
void Task::finishRefineIntervalWithBisector(TaskManager & man) {}

bool Task::computeSplitIntervalWithBisector(TaskManager& man) {
	GKBisector * bis = reinterpret_cast<GKBisector*>(dataPtr);
	Interval   * all = bis->getIntervalArray();
	int j = bis->split(localID);
//	count = 0;
	setCount(man, 0);
	if ( j > localID) {
		int i = localID;
		TaskID myID = man.myID(this);
		count   = 0; // create two tasks :) 
		localID = j; // use the lock in the middle of the interval
		TaskID taskID1 = -1, taskID2 = -1;
		if (man.allocateTaskID(taskID1, threadID)) {
			Task & task = man.getTask(taskID1);
			if (j - i > 1)
				task.reset(SplitIntervalWithBisector, bis, i, myID);
			else 
				task.reset(RefineIntervalWithBisector, bis, i, myID);
			man.addToReady(taskID1); 
			addCount(man, 1);
//			count++;
		}
		if (man.allocateTaskID(taskID2, threadID)) {
			Task & task = man.getTask(taskID2);
			if (all[j].count() > 1) 
				task.reset(SplitIntervalWithBisector, bis, j, myID);
			else 
				task.reset(RefineIntervalWithBisector, bis, j, myID);
			man.addToReady(taskID2); 
			addCount(man, 1);
//			count++;
		}
		return false;	
	} else 
		return true;
}
bool Task::childSplitIntervalWithBisector(TaskManager& man, 
			const TaskID childID){
	
	Lock & lock = man.getLock(localID + 1);
	lock.lock();
	bool res = (--count) == 0;
	lock.unlock();
	return res;
}
void Task::finishSplitIntervalWithBisector(TaskManager & man) {}


bool Task::computeIdentifyClusters(TaskManager& manager) {
	// check for valid input
	GKBisector * bis = reinterpret_cast<GKBisector*>(dataPtr);
	assert(bis != NULL);
	Interval * all = bis->getIntervalArray(); 
	assert(all != NULL);


	int nThreads = manager.getNThreads();
	localID  = nThreads;
	count    = localID;
	int * counts = new int[nThreads + 2]; 
	counts[nThreads + 1] = bis->getN();

	dataPtr = counts;

	TaskID myID = manager.myID(this);
	counts[0] = 0;
	for (int i = 0; i < localID; i++) {
		TaskID taskID;
		if (manager.allocateTaskID(taskID, threadID)) {
			counts[i+1] = -1;
			counts[i+2] = i < localID - 1 ? -1 :  bis->getN();
			Task & task = manager.getTask(taskID);
//			assert( manager.myID(&task) == taskID);
			task.reset(CountWithBisector, bis, i, myID);
			assert(task.parentID >= 0);
			manager.addToReady(taskID); 
		} else {
			addCount(manager, -1);
			assert(false);
		}
	}
	return false;
}
int Task::checkInterval(TaskManager& man, GKBisector* bis,  Interval * all,
			const int leftCount,	const int rightCount, const int step,
			const int nSteps,		const TaskID parentID) {
	assert( rightCount > leftCount);
	assert(all[leftCount].width == 1.0);
	all[leftCount].leftCount  = leftCount;
	all[leftCount].rightCount = rightCount;
	double left  = (bis->getMax() * (step + 0) ) / nSteps;
	double right = (bis->getMax() * (step + 1) ) / nSteps;

	all[leftCount].center = (left + right) / 2;
	all[leftCount].width  = (-left + right);
	TaskID taskID;
	if (man.allocateTaskID(taskID, threadID)) {
		Task & task = man.getTask(taskID);
		if (rightCount - leftCount > 1) {
			task.reset(SplitIntervalWithBisector , bis, leftCount, parentID);
		} else 
			task.reset(RefineIntervalWithBisector, bis, leftCount, parentID);
		man.addToReady(taskID); 
		return 1;
	} else {
		return 0;
	}
}
bool Task::childIdentifyClusters(TaskManager& man, const TaskID childID) {

	Task & child = man.getTask(childID);

	GKBisector* bis = reinterpret_cast<GKBisector*>(child.dataPtr);
	Interval * all = bis->getIntervalArray(); assert(all != NULL);
	TaskID myID = man.myID(this);

	int created = -1;
	if (child.type == CountWithBisector ) { // initial interval searching
		int * countArr = reinterpret_cast<int*>(dataPtr);
		int leftCount  = countArr[child.localID    ]; // this one can be -1
		int thisCount  = countArr[child.localID + 1]; // 
		int rightCount = countArr[child.localID + 2]; // 
		if ( leftCount != -1 && leftCount < thisCount && 
				all[leftCount].width == 0) {
			Lock & leftLock = man.getLock(child.localID + 1);
			leftLock.lock();
			if (all[leftCount].width == 0) {
				all[leftCount].width = 1.0;
				leftLock.unlock(); // quick unlock to reduce waiting time
				created += checkInterval(man, bis, all, leftCount, thisCount, 
							child.localID,  localID + 1, myID); 
			} else 
				leftLock.unlock();
			
		}

		if ( thisCount < rightCount && all[thisCount].width == 0) {
			Lock & thisLock = man.getLock(child.localID + 2);
			thisLock.lock();
			if (all[thisCount].width == 0) {
				all[thisCount].width = 1.0;
				thisLock.unlock();
				created += checkInterval(man, bis, all, thisCount, rightCount, 
							child.localID + 1,  localID + 1, myID); 
			} else 
				thisLock.unlock();
		}
	} else {

	}
	return addCount(man, created) == 0;
}
void Task::finishIdentifyClusters(TaskManager & man) {
	assert(count == 0);
	int * countArr = reinterpret_cast<int*>(dataPtr);
	delete[] countArr;

}
bool Task::computeShiftRepresentation(TaskManager& man) {

	return true;
}
bool Task::childShiftRepresentation(TaskManager& man, const TaskID childID) {

	return true;
}
void Task::finishShiftRepresentation(TaskManager & man) {
	assert(count == 0);

}

bool Task::computeCountWithBisector(TaskManager& manager) {
	GKBisector* bis = reinterpret_cast<GKBisector*>(dataPtr);
	Task & parent = manager.getTask(parentID);
	int * countArr = reinterpret_cast<int*>(parent.dataPtr);
	double x = (bis->getMax() * (localID + 1) ) / (parent.localID + 1);
	countArr[localID + 1] = bis->count(x);
	return true;
}
bool Task::childCountWithBisector(TaskManager&man, const TaskID childID) {
	assert(false);
	return true;
}
void Task::finishCountWithBisector(TaskManager & man) {
	assert(count == 0);
}

bool Task::computeComputeSingleton(TaskManager& man) {
	count = 0;	
	BiMRRR * bimrrr = reinterpret_cast<BiMRRR*>(dataPtr);
	const GK * parentGK = man.getGKManager()->getGK_safe(parentID);
	if (parentGK) { 
		bimrrr->computeSingleton(*parentGK, localID);
	} else 
		assert(false);
	return count == 0;
}
bool Task::childComputeSingleton(TaskManager& man,const TaskID childID) {
	assert(false);
	return true;
}
void Task::finishComputeSingleton(TaskManager & man) {
	assert(count == 0);
}

bool Task::computeComputeCluster(TaskManager& man) {
	TaskID myID = man.myID(this);
	GKManager * gkManager = man.getGKManager();
	GK *  myGK = gkManager->obtainGK(myID);
	int clusterStart   = localID;
	int clusterStop    = count;
	count              = clusterStop - clusterStart;
	int updateCount    = -count;
	assert(myGK->getRepresentation() == NGNPack);

	const GK & parent = *man.getGKManager()->getGK_safe(parentID);
	GK & child  = *myGK;
	double relShift = 0;

	BiMRRR * bimrrr = reinterpret_cast<BiMRRR*>(dataPtr);

	bimrrr->computeGoodChild   (parent, clusterStart, clusterStop, child, relShift);
	bimrrr->recallculateBorders(child , clusterStart, clusterStop,        relShift);
	updateCount += createSingeltonAndClustersTasks(man, bimrrr, clusterStart, clusterStop);
	int tmp;
	Lock & lock = man.getLock(this);
	lock.lock();
	tmp = (count += updateCount);
	lock.unlock();
	return tmp == 0;
}
bool Task::childComputeCluster(TaskManager& man, const TaskID childID) {
	int tmp = addCount(man, -1);
	if ( tmp == 0 ){
		TaskID myID = man.myID(this);
		man.getGKManager()->releaseGK(myID);
	}
	return tmp == 0;
}
void Task::finishComputeCluster(TaskManager & man) {	
	assert(count == 0);
}

bool Task::computeBiMRRRTask(TaskManager& man) {
	BiMRRR * bimrrr = reinterpret_cast<BiMRRR*>(dataPtr);
	TaskID myID = man.myID(this);
	GKManager * gkManager = man.getGKManager();
	assert(gkManager != NULL);

	gkManager->setNat(bimrrr->getNat());
	GK *  natGK = gkManager->obtainGK(myID);
	
	natGK->setRepresentation(Native);
	natGK->shiftFrom(*bimrrr->getNat(), 0);

	setCount(man, 1);

	TaskID taskID;
	if (man.allocateTaskID(taskID, threadID)) {
		Task & t = man.getTask(taskID);
		GKBisector * bis = bimrrr->getBis();
		t.reset(Task::IdentifyClusters, bis, 0, myID);
		man.addToReady(taskID);

		return false;
	} else {
		count = 0;
		return true;
	}

}
int Task::createSingeltonAndClustersTasks(TaskManager & man, BiMRRR * bimrrr, int start, int stop) const {
	// createSingelton and cluster tasks
	const double gapTol = bimrrr->getGapTol();
	Interval * all = bimrrr->getAll();
	TaskID myID  = man.myID(this);

	int i = start, startCluster = start, stopCluster = stop, updateCount = 0;
	while (i <= stop) {
		int j = all[i].rightCount;
		if (j > stop || !all[i].isClustered(gapTol, all[j])) {
			stopCluster = all[i].rightCount - 1;
			TaskID taskID1;
			if (man.allocateTaskID(taskID1, threadID)) {
				Task & task = man.getTask(taskID1);
				if (stopCluster == startCluster) { // singleton found
					task.reset(Task::ComputeSingleton, bimrrr,
						startCluster, myID);
				} else { // cluster found
					task.reset(Task::ComputeCluster, bimrrr,
						startCluster, myID);
					// use count field to pass stopCluster
					task.count = stopCluster;
				}
			} else {
				MISSING;
			}
			man.addToReady(taskID1);
			updateCount++;
			startCluster = j;
		}
		i = j;
	}
	return updateCount;
}
bool Task::childBiMRRRTask(TaskManager& man, const TaskID childID ) {
	Task & child = man.getTask(childID);
	TaskID myID  = man.myID(this);
	switch (child.getType()) {
		case (IdentifyClusters) : {
			BiMRRR * bimrrr = reinterpret_cast<BiMRRR*>(dataPtr);
			int n = bimrrr->getN();
			Lock & lock = man.getLockForTask(myID);
			lock.lock(); count += n; lock.unlock();
			int updateCount = -1 - n; // -1 because IdentifyCluster task finished
			updateCount += createSingeltonAndClustersTasks(man, bimrrr, 0, n-1);
			lock.lock(); count += updateCount;	lock.unlock();
			break;
		}
		case (ComputeCluster)   : {}
		case (ComputeSingleton)  : {
			Lock & lock = man.getLockForTask(myID);
			lock.lock();	count--;	lock.unlock();
			break;
		}
		default : {
			MISSING;
			break;
		}
	}
	if (count == 0) {
		man.getGKManager()->releaseGK(myID);
	}
	return count == 0;
}
void Task::finishBiMRRRTask(TaskManager & man) {
	BiMRRR * bimrrr = reinterpret_cast<BiMRRR*>(dataPtr);
	bimrrr->doneComputing();
}


class TestIdentifyClusters : public UnitTest {
public:
	TestIdentifyClusters ();
	virtual ~TestIdentifyClusters (){};
	virtual bool test() const;
};

TestIdentifyClusters::TestIdentifyClusters() {
	setName 				("Test IdentifyClusters");
	setDescription  	("Test IdentifyClusters for correct bahaviour & memory allocation");
	setTestAuthor		("Yordan Madzhunkov");
	setDeveloperAuthor("Yordan Madzhunkov");
	setCompileTime    (__DATE__, __TIME__); // each class that inherits this one should also have this line.
};

bool TestIdentifyClusters::test() const {
	TaskManager manager;
	const int n = 10;
	double dHard [] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
		1.0/8, 2.0/8, 3.0/8,	4.0/8, 5.0/8, 6.0/8, 7.0/8, 8.0/8, 9.0/8};
	Matrix B(n, n, BiDiagonal, dHard); assert(B.isUpper());
	GK nat(B, 0);
	GKBisector bis( nat ) ;
	bis.setRelAcc(1e-8);
//	cout << "A " << endl;
	Interval all[n]; memset(all, 0, sizeof(all));
	bis.setIntervalArray(all);
//	cout << bis.getMax() << endl;
	Task t;
	t.reset(Task::IdentifyClusters, &bis, 0, -1);
	manager.setN(n);
//	cout << "\n\n preform" << endl;
	manager.perform(t, 3);
//	cout << " collect " << endl;
	int i = 0;
	int startCluster = 0;
	int stopCluster = 0;
	double gapTol = 1e-3;
	int nSingletons = 0, nClusters = 0;
	while (i < n) {
		int j = all[i].rightCount;
		if (j == n || !all[i].isClustered(gapTol, all[j])) {
			stopCluster = all[i].rightCount - 1;
			if (stopCluster == startCluster) { // singleton found
				nSingletons++;
				// add in queue singleton task
//				cout << "Singleton found " << i << endl;
//				cout << all[i];
				// refine it to full accuracy
//				refine(all[i]);
			} else { // cluster found
				nClusters++;
				// add in queue cluster task
//				cout << "Cluster found " << startCluster << " " << 
//					stopCluster << endl;
			}
			startCluster = j;
		}
		i = j;
	}

	return nSingletons == 10 && nClusters == 0;
//	return false;
}

class TestBiMRRRTask : public UnitTest {
public:
	TestBiMRRRTask ();
	virtual ~TestBiMRRRTask (){};
	virtual bool test() const;
};

TestBiMRRRTask::TestBiMRRRTask() {
	setName 				("Test BiMRRRTask");
	setDescription  	("Test BiMRRRTask for correct bahaviour & memory allocation");
	setTestAuthor		("Yordan Madzhunkov");
	setDeveloperAuthor("Yordan Madzhunkov");
	setCompileTime    (__DATE__, __TIME__); // each class that inherits this one should also have this line.
};

bool TestBiMRRRTask::test() const {
	const int n = 10;
	double dEasy[2 * n]; 
	for (int i = 0; i < n; i++) dEasy[i] = i + 1.0;
	for (int i = n; i < 2 * n - 1; i++) dEasy[i] = (i + 1.0 - n) * 0.125;

	Matrix B(n, n, BiDiagonal, dEasy); assert(B.isUpper());
	Matrix U(n, n, Orthogonal);
	Matrix V(n, n, Orthogonal);
	Matrix S(n, n, Diagonal  );

	BiMRRR * bimrrr = new BiMRRR();
	bimrrr->setForComputing(B, U, S, V);
	TaskManager manager;
	manager.setN(bimrrr->getN());
	Task t;
	t.reset(Task::BiMRRRTask, bimrrr, 0, -1);
	manager.perform(t, 2);
	bimrrr->doneComputing();
	
//	cout << "residual = " << (B -  U * S * V).nrm2() / (n * B.nrm2() * DBL_EPSILON)<< endl;

	double k = 1.0e-8 / 8;
	double d2 = 1e-8;
	double dHard [] = {1 + d2, 1-5 * d2, 4, 1 + 2 * d2, 1, 2 + d2, 2 + 2 * d2, 
		2 + 3 * d2, 3 + d2, 3 + 2 * d2, 
		k, 2 * k, 3 * k, 4 * k, 5 * k, 6 * k, 7 * k, 8 * k, 9 * k};
	Matrix B2(n, n, BiDiagonal, dHard); assert(B.isUpper());
	bimrrr->setForComputing(B2, U, S, V);
	t.reset(Task::BiMRRRTask, bimrrr, 0, -1);
	manager.perform(t, 3);
	bimrrr->doneComputing();
	delObj(bimrrr);
//	return false;
	return (B2 * V.T() - U * S).nrm2() /  ( n * B2.nrm2() * DBL_EPSILON) < 5;
}
TestIdentifyClusters testIdentifyClusters;
TestBiMRRRTask  testBiMRRRTask;
